package Offer07_重建二叉树;


import java.util.Stack;

/**
 * ---------------------------------------------------------------------
 * 题目：
 *      输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *      假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * ---------------------------------------------------------------------
 * 示例:
 *      Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 *      Output: [3,9,20,null,null,15,7]
 * ---------------------------------------------------------------------
 * 方法：
 *
 * ---------------------------------------------------------------------
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public static void main(String[] args) {
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        buildTree(preorder,inorder);
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int index=0;
        for(int i=1;i<preorder.length;++i){
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if(node.val!=inorder[index]){
                node.left=new TreeNode(preorderVal);
                stack.push(node.left);
            }else{
                while(!stack.empty()&&stack.peek().val==inorder[index]){
                    node=stack.pop();
                    index++;
                }
                node.right=new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}